package queens;

public class Queens {

	private static int solutionNum;

	public static void fillCloumn(int c, boolean[][] bord, int n) {
		if (c == n) {
			solutionNum++;
//            for (int i = 0; i < bord.length; i++) {
//                boolean[] bs = bord[i];
//                for (int j = 0; j < bs.length; j++) {
//                    boolean b = bs[j];
//                    System.out.print(b ? "x " : ". ");
//                }
//                System.out.println();
//            }
//            System.out.println();
		} else {
			for (int r = 0; r < n; r++) {
				if (isAvialble(bord, c, r, n)) {
					bord[c][r] = true;
					fillCloumn(c + 1, bord, n);
					bord[c][r] = false;
				}

			}
		}
	}

	public static int queens(int n) {
		solutionNum = 0;
		fillCloumn(0, new boolean[n][n], n);
		return solutionNum;
	}

	public static void main(String[] args) {
		for (int i = 0; i < 12; i++) {
			System.out.println(queens(i));
		}
	}

	private static boolean isAvialble(boolean[][] bord, int col, int row, int n) {
		for (int i = 0; i < col; i++) {
			if (bord[i][row]) {
				return false;
			}
			int up = row - i - 1;
			if (up >= 0 && bord[col - i - 1][up]) {
				return false;
			}

			int down = row + i + 1;
			if (down < n && bord[col - i - 1][down]) {
				return false;
			}
		}
		return true;
	}
}
